"""
https://leetcode.cn/problems/trapping-rain-water/description/

42. 接雨水
已解答
困难
相关标签
premium lock icon
相关企业
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

 

示例 1：



输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
示例 2：

输入：height = [4,2,0,3,2,5]
输出：9
 

提示：

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

"""

from typing import List


class Solution:
    """
    接雨水的题目，有一个共性可参考。
    接到的雨水高度，必定在左侧和右侧各有一个边界。雨水高度为该边界的较小值。

    考虑分别记录每一个x坐标的左右最大坐标。

    """

    def trap(self, height: List[int]) -> int:
        left_max=[]
        right_max=[]
        mh=0
        for i in range(0,len(height)):
            left_max.append(mh)
            mh=max(mh,height[i])
        mh=0
        for i in range(len(height)-1,-1,-1):
            right_max.append(mh)
            mh=max(mh,height[i])
        right_max=right_max[::-1]
        
        sum=0
        for i,h in enumerate(height):
            if left_max[i]>h and right_max[i]>h:
                sum+=(min(left_max[i],right_max[i])-h)
            
        return sum

if __name__=='__main__':
    height = [4,2,0,3,2,5]

    sol=Solution()
    res=sol.trap(height)
    print(res)
    pass